package com.example.sequence.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author SongXuSheng
 * @description: 希尔排序
 * @date 2022/8/1 21:47
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {5,8,3,4,1,10,7,2,9,6};
        int gap=arr.length;
        while (gap>1){
            gap=gap/3+1;
            for (int i = gap; i < arr.length; i++) {
                int key = arr[i];
                int end = i - gap;
                while (end >= 0 && arr[end] > key) {
                    arr[end + gap] = arr[end];
                    end-=gap;
                }
                arr[end + gap] = key;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
